<!DOCTYPE html>
<html lang="zh-CN">
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1" />
    <title>数据挖掘 | Data Mining Course</title>
    <link rel="stylesheet" href="../../css/main.css" />
    <link rel="stylesheet" href="../../css/tabs.css" />
    <script src="../../js/uikit.js"></script>
    <link href="../../css/prism.css" rel="stylesheet" />
    <script src="../../js/prism.js"></script>
  </head>

  <body>
    <div
      data-uk-sticky="animation: uk-animation-slide-top; sel-target: .uk-navbar-container; cls-active: uk-navbar-sticky; cls-inactive: uk-navbar-transparent; top: 300"
    >
      <nav class="uk-navbar-container pt-2 pb-2">
        <div class="uk-container">
          <div data-uk-navbar>
            <div class="uk-navbar-left">
              <a
                class="uk-navbar-item uk-logo uk-visible@m"
                href="../../index.html"
                >数据挖掘课程</a
              >
              <a
                class="uk-navbar-tuk-containeroggle uk-hidden@m"
                href="#offcanvas-docs"
                data-uk-toggle
                ><span data-uk-navbar-toggle-icon></span>
                <span class="uk-margin-small-left">目录</span></a
              >
              <ul class="uk-navbar-nav uk-visible@m">
                <li><a href="../index.html">文档</a></li>
              </ul>
            </div>
            <div class="uk-navbar-center uk-hidden@m">
              <a class="uk-navbar-item uk-logo" href="../../index.html"
                >数据挖掘课程</a
              >
            </div>
          </div>
        </div>
      </nav>
    </div>

    <div class="uk-section">
      <div class="uk-container">
        <div class="uk-grid-large" data-uk-grid>
          <div class="sidebar-fixed-width uk-visible@m">
            <div class="sidebar-docs uk-position-fixed uk-margin-top">
              <h5>关于这门课</h5>
              <ul class="uk-nav uk-nav-default doc-nav">
                <li><a href="../../index.html">大纲</a></li>
              </ul>
              <h5>章节</h5>
              <ul class="uk-nav uk-nav-default doc-nav">
                <li><a href="../01.html">第1章 - 数据挖掘概念</a></li>
                <li><a href="../02.html">第2章 - 分类</a></li>
                <li><a href="../03.html">第3章 - 聚类</a></li>
                <li><a href="../04.html">第4章 - 关联规则</a></li>
                <li><a href="../05.html">第5章 - 日志的挖掘与应用</a></li>
                <li><a href="../06.html">第6章 - 数据挖掘应用案例</a></li>
              </ul>
              <h5>实验课</h5>
              <ul class="uk-nav uk-nav-default doc-nav">
                <li><a href="./code-01.html">01</a></li>
                <li><a href="./code-02.html">02</a></li>
                <li><a href="./code-03.html">03</a></li>
                <li><a href="./code-04.html">04</a></li>
                <li><a href="./code-05.html">05</a></li>
                <li class="uk-active"><a href="./code-06.html">06</a></li>
                <li><a href="./code-07.html">07</a></li>
                <li><a href="./code-08.html">08</a></li>
                <li><a href="./code-09.html">09</a></li>
                <li><a href="./code-10.html">10</a></li>
                <li><a href="./code-11.html">11</a></li>
                <li><a href="./code-12.html">12</a></li>
                <li><a href="./code-13.html">13</a></li>
                <li><a href="./code-14.html">14</a></li>
                <li><a href="./code-15.html">15</a></li>
                <li><a href="./code-16.html">16</a></li>
              </ul>
            </div>
          </div>
          <div class="uk-width-1-1 uk-width-expand@m">
            <article class="uk-article">
              <h2>关联规则之FP-growth算法</h2>
              <div>



                <h4>1. 建立FP树的类定义</h4>
                <p>复制下面7个步骤的代码到一个python文件中</p>
<pre><code class='language-python' lang='python'>class treeNode:
    def __init__(self, nameValue, numOccur, parentNode):
        self.name = nameValue     # 存放节点名字
        self.count = numOccur     # 存放计数值
        self.nodeLink = None      # 链接相似的元素项
        self.parent = parentNode  # 指向父节点
        self.children = {}        # 存放子节点

    def inc(self, numOccur):
        self.count += numOccur

    def disp(self, ind=1):
        print(&#39;  &#39;*ind, self.name, &#39; &#39;, self.count)
        for child in self.children.values():
            child.disp(ind+1)            
</code></pre>
                <h4>2.FP树构建函数</h4>
<pre><code class='language-python' lang='python'>def createFPTree(dataSet, minSup=1):
    headerTable = {}
    for trans in dataSet:
        for item in trans:
            headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
    for k in list(headerTable.keys()):
        if headerTable[k] &lt; minSup:
            del(headerTable[k]) # 删除不满足最小支持度的元素
    freqItemSet = set(headerTable.keys()) # 满足最小支持度的频繁项集
    if len(freqItemSet) == 0:
        return None, None
    for k in headerTable:
        headerTable[k] = [headerTable[k], None] # element: [count, node]

    retTree = treeNode(&#39;Null Set&#39;, 1, None)
    for tranSet, count in dataSet.items():
        # dataSet：[element, count]
        localD = {}
        for item in tranSet:
            if item in freqItemSet: # 过滤，只取该样本中满足最小支持度的频繁项
                localD[item] = headerTable[item][0] # element : count
        if len(localD) &gt; 0:
            # 根据全局频数从大到小对单样本排序
            orderedItem = [v[0] for v in sorted(localD.items(), key=lambda p:p[1], reverse=True)]
            # 用过滤且排序后的样本更新树
            updateFPtree(orderedItem, retTree, headerTable, count)
    return retTree, headerTable

def updateHeader(nodeToTest, targetNode):
    while nodeToTest.nodeLink != None:
        nodeToTest = nodeToTest.nodeLink
    nodeToTest.nodeLink = targetNode
def updateFPtree(items, inTree, headerTable, count):
    if items[0] in inTree.children:
        # 判断items的第一个结点是否已作为子结点
        inTree.children[items[0]].inc(count)
    else:
        # 创建新的分支
        inTree.children[items[0]] = treeNode(items[0], count, inTree)
        # 更新相应频繁项集的链表，往后添加
        if headerTable[items[0]][1] == None:
            headerTable[items[0]][1] = inTree.children[items[0]]
        else:
            updateHeader(headerTable[items[0]][1], inTree.children[items[0]])
    # 递归
    if len(items) &gt; 1:
        updateFPtree(items[1::], inTree.children[items[0]], headerTable, count)
</code></pre>
<h4>3.  制造一些数据</h4>
<pre><code class='language-python' lang='python'>def loadSimpDat():
    simpDat = [[&#39;r&#39;, &#39;z&#39;, &#39;h&#39;, &#39;j&#39;, &#39;p&#39;],
                [&#39;z&#39;, &#39;y&#39;, &#39;x&#39;, &#39;w&#39;, &#39;v&#39;, &#39;u&#39;, &#39;t&#39;, &#39;s&#39;],
                [&#39;z&#39;],
                [&#39;r&#39;, &#39;x&#39;, &#39;n&#39;, &#39;o&#39;, &#39;s&#39;],
                [&#39;y&#39;, &#39;r&#39;, &#39;x&#39;, &#39;z&#39;, &#39;q&#39;, &#39;t&#39;, &#39;p&#39;],
                [&#39;y&#39;, &#39;z&#39;, &#39;x&#39;, &#39;e&#39;, &#39;q&#39;, &#39;s&#39;, &#39;t&#39;, &#39;m&#39;]]
    return simpDat
</code></pre>
<h4>4.构造成 element : count 的形式，如 z:5, x:3</h4>
<pre><code class='language-python' lang='python'>def createInitSet(dataSet):
    retDict={}
    for trans in dataSet:
        key = frozenset(trans)
        if key in retDict:
            retDict[frozenset(trans)] += 1
        else:
            retDict[frozenset(trans)] = 1
    return retDict
</code></pre>
<h4>5.抽取条件模式基需要用到的函数</h4>
<pre><code class='language-python' lang='python'># 递归回溯树，从本节点一直往上
def ascendTree(leafNode,prefixPath):
    if leafNode.parent != None:
        prefixPath.append(leafNode.name)
        ascendTree(leafNode.parent,prefixPath)

# 找到需查找元素的所有前缀路径
def findPrefixPath(basePat,treeNode):
    condPats={}
    while treeNode != None:
        prefixPath=[]
        ascendTree(treeNode,prefixPath)
        if len(prefixPath)&gt;1:
            condPats[frozenset(prefixPath[1:])]=treeNode.count
        treeNode=treeNode.nodeLink
    return condPats
</code></pre>
<h4>6. 创建条件FP树，挖掘树中的信息</h4>
<pre><code class='language-python' lang='python'>def mineTree(inTree,headerTable,minSup,preFix,freqItemList):
    # 此处原文有错误
    # 从头指针的底端开始
    bigL=[v[0] for v in sorted(headerTable.items(),key=lambda p:p[0])]
    for basePat in bigL:
        newFreqSet=preFix.copy()
        newFreqSet.add(basePat)
        freqItemList.append(newFreqSet)
        # 创建条件基
        condPattBases=findPrefixPath(basePat,headerTable[basePat][1])
        # 创造条件fp树
        myCondTree,myHead=createFPTree(condPattBases,minSup)
        # 递归找到满足阈值的项
        # myHead==None 时，说明树只有一层叶节点，即频繁次项为一元
        if myHead!=None:
            print(&#39;conditional tree for:&#39;,newFreqSet)
            myCondTree.disp(1)
            mineTree(myCondTree,myHead,minSup,newFreqSet,freqItemList)
</code></pre>
<h4>7.跑起来</h4>
<pre><code class='language-python' lang='python'>print(&quot;构建FP树：&quot;)
min_sup = 3 # 最小支持度3
simDat = loadSimpDat()
initSet = createInitSet(simDat)
myFPtree, myHeaderTab = createFPTree(initSet, min_sup)
myFPtree.disp()

print(&quot;================&quot;)
print(&quot;抽取条件模式基：&quot;)
for item in list(myHeaderTab.keys()):
    print(findPrefixPath(item,myHeaderTab[item][1]))

print(&quot;================&quot;)
print(&quot;挖掘出频繁项集：&quot;)
freqItems=[]
c=mineTree(myFPtree,myHeaderTab,3,set([]),freqItems)
print(freqItems)
</code></pre>
<h4>8.说明一下</h4>
<p>对于这颗构建的FP树</p>
<img src="../../images/lab06/o1.JPG" alt="">
<p>它其实是这个意思</p>
<img src="../../images/lab06/output.JPG" alt="">            
<p>要反应的是下面这样的树结构</p>
<img src="../../images/lab06/fp-tree.png" alt="">   
<p>打印出来的条件模式基</p>   
<img src="../../images/lab06/cpb.JPG" alt="cpb">
<p>其实反应的就是咱们课上说的这个表</p>   
<img src="../../images/lab06/cpb-table.png" alt="cpb-table">
<p>最后，这里打印出来的是频繁项集</p>  
<img src="../../images/lab06/f-items.JPG" alt="items">
                
              </div>
            </article>
          </div>
        </div>
      </div>
    </div>

    <div id="offcanvas-docs" data-uk-offcanvas="overlay: true">
      <div class="uk-offcanvas-bar">
        <button class="uk-offcanvas-close" type="button" data-uk-close></button>
        <h5 class="uk-margin-top">关于这门课</h5>
        <ul class="uk-nav uk-nav-default doc-nav">
          <li><a href="../indext.html">大纲</a></li>
        </ul>
        <h5 class="uk-margin-top">章节</h5>
        <ul class="uk-nav uk-nav-default doc-nav">
          <li><a href="../01.html">第1章 - 数据挖掘概念</a></li>
          <li><a href="../02.html">第2章 - 分类</a></li>
          <li><a href="../03.html">第3章 - 聚类</a></li>
          <li><a href="../04.html">第4章 - 关联规则</a></li>
          <li><a href="../05.html">第5章 - 日志的挖掘与应用</a></li>
          <li><a href="../06.html">第6章 - 数据挖掘应用案例</a></li>
        </ul>
        <h5>实验课</h5>
        <ul class="uk-nav uk-nav-default doc-nav">
          <li><a href="./code-01.html">01</a></li>
          <li><a href="./code-02.html">02</a></li>
          <li><a href="./code-03.html">03</a></li>
          <li><a href="./code-04.html">04</a></li>
          <li><a href="./code-05.html">05</a></li>
          <li class="uk-active"><a href="./code-06.html">06</a></li>
          <li><a href="./code-07.html">07</a></li>
          <li><a href="./code-08.html">08</a></li>
          <li><a href="./code-09.html">09</a></li>
          <li><a href="./code-10.html">10</a></li>
          <li><a href="./code-11.html">11</a></li>
          <li><a href="./code-12.html">12</a></li>
          <li><a href="./code-13.html">13</a></li>
          <li><a href="./code-14.html">14</a></li>
          <li><a href="./code-15.html">15</a></li>
          <li><a href="./code-16.html">16</a></li>
        </ul>
      </div>
    </div>

    <footer class="uk-section uk-text-center uk-text-muted">
      <div class="uk-container uk-container-small">
        <div class="uk-margin-medium"></div>
      </div>
    </footer>

    <script src="../js/awesomplete.js"></script>
    <script src="../js/custom.js"></script>
  </body>
</html>
